package j2024.j202412;



public class j1226 {
    /**
     * 108. 将有序数组转换为二叉搜索树
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
     * 平衡
     *  二叉搜索树。
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return ToBST(nums, 0, nums.length - 1);
    }
    public TreeNode ToBST(int[] nums,int left, int right){
        if(left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = ToBST(nums, left, mid - 1);
        root.right = ToBST(nums, mid + 1, right);
        return root;
    }

    /**
     * 98. 验证二叉搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     *
     * 有效 二叉搜索树定义如下：
     *
     * 节点的左
     * 子树
     * 只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     */
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        //前
        boolean left = isValidBST(root.left);
        if(!left) return false;
        //中
        boolean mid = false;
        if(prev < root.val) mid = true;
        else return false;
        prev = root.val;
        //后
        boolean right = isValidBST(root.right);
        if(!right) return false;
        return left && mid && right;
    }

    /**
     * 230. 二叉搜索树中第 K 小的元素
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
     */
    int ret = 0;
    int count;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    public void dfs(TreeNode root) {
        if(root == null || count==0) return;
        dfs(root.left);
        if(count==0) return;
        ret = root.val;
        count--;
        dfs(root.right);
    }
}
